package searchUtil;

/**
 * @Author: sun
 * @Description:
 * @Data: create in 15:37 2018/12/17
 * @Modfied by:
 */

import hashUtil.BBox;
import hashUtil.BBoxPrefix;
import hashUtil.GeoHashUtil;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import org.geotools.geometry.jts.JTSFactoryFinder;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LinearRing;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;

/**
 * 这个还需要补充
 * @author QiuFeng
 *
 */
public class GetHashRange {
	/**
	 * 默认使用DFS搜索的方式
	 * @param str
	 * @return
	 * @throws ParseException
	 */
	public static ArrayList<long[]> getHashRange(String str) throws ParseException{
		return getHashRange(str, true);
	}

	/**
	 *
	 * @param str
	 * @param dfs_bfs true使用DFS，false使用BFS
	 * @return
	 * @throws ParseException
	 */
	public static ArrayList<long[]> getHashRange(String str, boolean dfs_bfs) throws ParseException{
		String[] strArr = str.split(":");
		String type = strArr[0].trim();
		//--------------------------------------
		//圆形
		if(type.equalsIgnoreCase("c") || type.equalsIgnoreCase("circle")){
			System.out.println("circle");
			//TODO 注意深度
			return dfs_bfs?searchCircleByDFS(strArr[1],10):searchCircleByBFS(strArr[1], 10, 1.5);
		}
		//--------------------------------------
		//矩形
		else if(type.equalsIgnoreCase("r") || type.equalsIgnoreCase("rectangle")){
			System.out.println("rectangle");
			//TODO 注意深度
			return dfs_bfs?searchRectangleByDFS(strArr[1],12):searchRectangleByBFS(strArr[1], 12, 1.8);

		}
		//--------------------------------------
		//多边形
		else if(type.equalsIgnoreCase("p") || type.equalsIgnoreCase("polygon")){
			System.out.println("polygon");
			//TODO 注意深度
			return dfs_bfs?searchPolyByDFS(strArr[1],12):searchPolyByBFS(strArr[1], 12, 1.8);

		}
		else {
			try {
				throw new Exception("the input's type is wrong, please check! (type+\":\"+info), the must be circle(c),  polygon(p) or rectangle(r)");
			} catch (Exception e) {
				e.printStackTrace();
			}
//			System.err.println("输入参数中类型错误(字符串中冒号前的部分)，请检查，正常的格式是：type+\":\"+info.");
			return null;
		}
	}

    /**
     * 查询一个多边形对应的区域中包含的hash段，由参数polygon 来表示该多边形，
     * polygon为String 类型，polygon只包含了若干点的坐标。并且需要满足WKT
     * 中对多边形的描述的要求。例如：POLYGON((0 0,10 0,10 10,0 10,0 0))，
     * 注意首尾点是同一个点。<br>
     * 搜索采用的<b>深度优先</b>(但是对深度加了一个限制)，也可以采用广度优先，效果应该
     * 是一样的。但是如果要涉及到与面积相关的要求时，应该采用广度优先遍历。
     * @param polygon 字符串，用于描述若干点，各点之间用逗号隔开，每个点的横纵坐标用空格隔开。
     * @param deepth 搜索深度
     * @return 若干hash段
     * @throws ParseException 输入polygon有误
     */
    public static ArrayList<long[]> searchPolyByDFS(String polygon, int deepth) throws ParseException {
    	//利用JTS包，来帮助判断多边形。
    	GeometryFactory factory = JTSFactoryFinder.getGeometryFactory(null);
    	WKTReader reader = new WKTReader(factory);
//    	System.out.println("POLYGON(("+polygon+"))");
		Polygon poly = (Polygon) reader.read("POLYGON(("+polygon+"))");
        //返回的结果
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        double boundary[] = getMinRect(polygon);//获取多边形边界，即外接矩形，左 右 上 下
        BBox searchBox = new BBox(boundary[2], boundary[0], boundary[3], boundary[1]);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        Stack<BBoxPrefix> searchStack = new Stack<BBoxPrefix>();
        //init 将最开始的最大公共前缀放入，这里在栈中直接存储的是每个节点上对应的BBoxPrefix
        searchStack.push(bBoxPrefix);
        //还是深度优先搜索二叉树，补0、补1
        while (!searchStack.isEmpty()){
            BBoxPrefix prefixNow = searchStack.pop();
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            Polygon bB = box2Polygon(prefixBBox);
            //如果被包含了，那么停止，不再继续向下搜索
            if(poly.contains(bB)){
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }else if(prefixNow.length-bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                //左树1，右树0，先左后右 再判断是否超出搜索的深度
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                /////////////////////////////////////////
                if(poly.intersects(box2Polygon(attachZeroBbox))){
                	searchStack.push(attachZero);
                }
                if(poly.intersects(box2Polygon(attachOneBbox))){
                	searchStack.push(attachOne);
                }
            }else {
                //超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }
        }
        //hash 段的排序与合并
        sortCombine(ResultSet);
//        System.out.println(ResultSet.size());
        return ResultSet;
    }

    public static ArrayList<long[]> searchPolyByBFS(String polygon, int deepth, double rate) throws ParseException {
    	//利用JTS包，来帮助判断多边形。
    	GeometryFactory factory = JTSFactoryFinder.getGeometryFactory(null);
    	WKTReader reader = new WKTReader(factory);
//    	System.out.println("POLYGON(("+polygon+"))");
		Polygon poly = (Polygon) reader.read("POLYGON(("+polygon+"))");
        //返回的结果
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        int prefixlen = 0;
        double S = poly.getArea();
        double SAll = 0.0;
        double boundary[] = getMinRect(polygon);//获取多边形边界，即外接矩形，左 右 上 下
        BBox searchBox = new BBox(boundary[2], boundary[0], boundary[3], boundary[1]);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        Queue<BBoxPrefix> searchQueue = (Queue<BBoxPrefix>) new LinkedList<BBoxPrefix>();
        //init 将最开始的最大公共前缀放入，这里在栈中直接存储的是每个节点上对应的BBoxPrefix
        searchQueue.add(bBoxPrefix);
        SAll += GeoHashUtil.GetArea4Prefix(bBoxPrefix);
        System.out.println("S:"+S);
        //还是宽度优先搜索二叉树，补0、补1
        while (!searchQueue.isEmpty()){
            BBoxPrefix prefixNow = searchQueue.poll();
            SAll -= GeoHashUtil.GetArea4Prefix(prefixNow);
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            Polygon bB = box2Polygon(prefixBBox);
            //如果被包含了，那么停止，不再继续向下搜索
            if(poly.contains(bB)){
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
                SAll += (prefixBBox.topRightLat - prefixBBox.bottomLeftLat) * (prefixBBox.topRightLon - prefixBBox.bottomLeftLon);
            }else if(prefixNow.length-bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                //左树1，右树0，先左后右 再判断是否超出搜索的深度
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                /////////////////////////////////////////
                if(poly.intersects(box2Polygon(attachZeroBbox))){
                	searchQueue.add(attachZero);
                	SAll += GeoHashUtil.GetArea4Prefix(attachZero);
                }
                if(poly.intersects(box2Polygon(attachOneBbox))){
                	searchQueue.add(attachOne);
                	SAll += GeoHashUtil.GetArea4Prefix(attachOne);
                }
            }else {
                //超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
                SAll += (prefixBBox.topRightLat - prefixBBox.bottomLeftLat) * (prefixBBox.topRightLon - prefixBBox.bottomLeftLon);
            }
            if(SAll/S < rate && prefixlen != prefixNow.length){
            	while(!searchQueue.isEmpty()){
            		long[] hashFromTo = new long[2];
            		BBoxPrefix prefix = searchQueue.poll();
            		hashFromTo[0] = prefix.prefix;
                    hashFromTo[1] = (0xffffffffffffffffL >>> prefix.length) + prefix.prefix;
                    ResultSet.add(hashFromTo);
            	}
            	break;
            }
            System.out.print(ResultSet.size()+" ");
            System.out.println(SAll/S+" "+SAll+" "+S+" "+prefixNow.length+" "+prefixlen+" "+bBoxPrefix.length+" "+searchQueue.size());
            prefixlen = prefixNow.length;
        }
        System.out.println(areas(ResultSet));
        //hash 段的排序与合并
        sortCombine(ResultSet);
//        System.out.println(ResultSet.size());
        return ResultSet;
    }


    public static ArrayList<long[]> searchRectangleByBFS(String rectangle, int deepth, double rate) {
        double bottomLeftLon, bottomLeftLat, topRightLon, topRightLat;
        String[] arr = rectangle.split(",");
        double[] pt = new double[4];
        for(int i = 0; i < 4; i++){
			pt[i] = Double.parseDouble(arr[i].trim());
		}
        //TODO 这个对于点的检查应该考虑放在构造函数中
        bottomLeftLon = Math.min(pt[0], pt[2]);//左下角经度
        bottomLeftLat = Math.min(pt[1], pt[3]);//左下角纬度
        topRightLon = Math.max(pt[0], pt[2]);//右上角经度
		topRightLat = Math.max(pt[1], pt[3]);//右上角纬度

		//最开始的查询 查询 查询矩形的面积
		final double S = (topRightLat - bottomLeftLat) * (topRightLon - bottomLeftLon);
		//hash段对应矩形的面积
		double SAll = 0.0;
//		int lastBoxPreLen = -1;
		//结果的返回容器
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        //searchBox，最开始的查询矩形框
        BBox searchBox = new BBox(bottomLeftLon, bottomLeftLat, topRightLon, topRightLat);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        Queue<BBoxPrefix> searchQueue = (Queue<BBoxPrefix>) new LinkedList<BBoxPrefix>();
        int prefixlen = 0;
        //init 将最开始的最大公共前缀放入，这里在队列中直接存储的是每个节点上对应的BBoxPrefix
        searchQueue.add(bBoxPrefix);
        SAll += GeoHashUtil.GetArea4Prefix(bBoxPrefix);
        //改为BFS，为了利用面积来限制循环，而求面积需要在搜索的同一层中，所以利用BFS，其实
        //TODO：在这里没有对面积限制进行处理，有需求的话，可以在修改
        while (!searchQueue.isEmpty()){
        	BBoxPrefix prefixNow = searchQueue.poll();
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            SAll -= GeoHashUtil.GetArea4Prefix(prefixNow);
            //如果被包含了，那么停止，不再继续向下搜索
            if(searchBox.contain(prefixBBox)){
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
                SAll += (prefixBBox.topRightLat - prefixBBox.bottomLeftLat) * (prefixBBox.topRightLon - prefixBBox.bottomLeftLon);
            }else if(prefixNow.length - bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                //左树1，右树0，先左后右 再判断是否超出搜索的深度
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                if(searchBox.interset(attachZeroBbox)) {
                	searchQueue.add(attachZero);
                	SAll += GeoHashUtil.GetArea4Prefix(attachZero);
                }
                if(searchBox.interset(attachOneBbox)){
                	searchQueue.add(attachOne);
                	SAll += GeoHashUtil.GetArea4Prefix(attachOne);
                }

            }else {
                //搜索深度超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
                SAll += (prefixBBox.topRightLat - prefixBBox.bottomLeftLat) * (prefixBBox.topRightLon - prefixBBox.bottomLeftLon);
            }
            if(SAll/S < rate && prefixlen != prefixNow.length){
            	while(!searchQueue.isEmpty()){
            		long[] hashFromTo = new long[2];
            		BBoxPrefix prefix = searchQueue.poll();
            		hashFromTo[0] = prefix.prefix;
                    hashFromTo[1] = (0xffffffffffffffffL >>> prefix.length) + prefix.prefix;
                    ResultSet.add(hashFromTo);
            	}
            	break;
            }
            System.out.print(ResultSet.size()+" ");
            System.out.println(SAll/S+" "+SAll+" "+S+" "+prefixNow.length+" "+prefixlen+" "+bBoxPrefix.length+" "+searchQueue.size());
            prefixlen = prefixNow.length;

        }
      //hash 段的排序与合并
        System.out.println(areas(ResultSet)+" "+S);
        sortCombine(ResultSet);
        System.out.println(ResultSet.size());
        return ResultSet;
    }

    /**
	 * 传入包含2个顶点信息的矩形，利用DFS遍历返回
	 * 一个hash 段集合。
	 *
	 * @param rectangle 有4个浮点数构成，并有逗号隔开的字符串
	 * @param deepth 递归的深度限制
	 * @return 一个Geohash 段的List
	 */
    public static ArrayList<long[]> searchRectangleByDFS(String rectangle, int deepth) {
        double bottomLeftLon, bottomLeftLat, topRightLon, topRightLat;
        String[] arr = rectangle.split(",");
        double[] pt = new double[4];
        for(int i = 0; i < 4; i++){
			pt[i] = Double.parseDouble(arr[i].trim());
		}
        //TODO 这个对于点的检查应该考虑放在构造函数中
        bottomLeftLon = Math.min(pt[0], pt[2]);//左下角经度
        bottomLeftLat = Math.min(pt[1], pt[3]);//左下角纬度
        topRightLon = Math.max(pt[0], pt[2]);//右上角经度
		topRightLat = Math.max(pt[1], pt[3]);//右上角纬度

		//结果的返回容器
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        //searchBox，最开始的查询矩形框
        BBox searchBox = new BBox(bottomLeftLon, bottomLeftLat, topRightLon, topRightLat);
        System.out.println("searchBox "+searchBox);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        Stack<BBoxPrefix> searchStack = new Stack<BBoxPrefix>();
        //DFS
        //init 将最开始的最大公共前缀放入，这里在队列中直接存储的是每个节点上对应的BBoxPrefix
        searchStack.push(bBoxPrefix);
        while (!searchStack.isEmpty()){
        	BBoxPrefix prefixNow = searchStack.pop();
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            //如果被包含了，那么停止，不再继续向下搜索
            if(searchBox.contain(prefixBBox)){
                long[] hashFromTo = new long[3];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }else if(prefixNow.length - bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                //左树1，右树0，先左后右 再判断是否超出搜索的深度
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                if(searchBox.interset(attachZeroBbox)) {
                	searchStack.push(attachZero);
                }
                if(searchBox.interset(attachOneBbox)){
                	searchStack.push(attachOne);
                }

            }else {
                //搜索深度超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }

        }
      //hash 段的排序与合并
        sortCombine(ResultSet);
        return ResultSet;
    }

    /**
     *
     * @param circle
     * @param deepth
     * @return
     * @throws ParseException
     */
    public static ArrayList<long[]> searchCircleByBFS(String circle, int deepth, double rate) throws ParseException{
    	//返回的结果
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        //JTS 中的内容
        GeometryFactory factory = JTSFactoryFinder.getGeometryFactory(null);
    	WKTReader reader = new WKTReader(factory);
        double topRightLat, bottomLeftLon, bottomLeftLat, topRightLon;
    	String[] arr = circle.split(",");
    	//3个元素 横纵坐标，半径
    	double x = Double.parseDouble(arr[0].trim()),
    			y = Double.parseDouble(arr[1].trim()),
    			r = Double.parseDouble(arr[2].trim());
    	bottomLeftLon = x - r;//经度，x
    	topRightLat = y + r;//纬度，y
    	topRightLon = x + r;
    	bottomLeftLat = y - r;
    	double SAll = 0.0;
    	double S = Math.PI * r * r;
    	Point center = (Point) reader.read("POINT("+x+" "+y+")");
    	if(r <= 0){
    		System.err.println("圆的半径不能为非正数");
    		return null;
    	}
    	if(bottomLeftLon < -180 || topRightLat > 90 || topRightLon > 180 || bottomLeftLat < -90 ){
    		System.err.println("圆跨边界，暂不支持");
    		return null;
    	}

    	Polygon cir = createCircle(x, y, r, 32);
    	//外切正方形（矩形）。
        BBox searchBox = new BBox(topRightLat, bottomLeftLon, bottomLeftLat, topRightLon);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        Queue<BBoxPrefix> searchQueue = (Queue<BBoxPrefix>) new LinkedList<BBoxPrefix>();
        //init 将最开始的最大公共前缀放入，这里在栈中直接存储的是每个节点上对应的BBoxPrefix 虽然深度优先不会占用太多内存，(前缀的长度需要知道)
        searchQueue.add(bBoxPrefix);
        SAll += GeoHashUtil.GetArea4Prefix(bBoxPrefix);
        int prefixlen = 0;
        //还是宽度优先搜索二叉树
        while (!searchQueue.isEmpty()){
            BBoxPrefix prefixNow = searchQueue.poll();
            SAll -= GeoHashUtil.GetArea4Prefix(prefixNow);
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            Polygon bB = box2Polygon(prefixBBox);
            //如果被包含了，那么停止，不再继续向下搜索
            if(cir.contains(bB)){
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
//                SAll += (prefixBBox.topRightLat - prefixBBox.bottomLeftLat) * (prefixBBox.topRightLon - prefixBBox.bottomLeftLon);
            }else if(prefixNow.length-bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                //左树1，右树0，先左后右 再判断是否超出搜索的深度
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                if(cir.intersects(box2Polygon(attachZeroBbox))){
                	searchQueue.add(attachZero);
                	SAll += GeoHashUtil.GetArea4Prefix(attachZero);
                }
                if(cir.intersects(box2Polygon(attachOneBbox))){
                	searchQueue.add(attachOne);
                	SAll += GeoHashUtil.GetArea4Prefix(attachOne);
                }
            }else {
                //超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
//                SAll += (prefixBBox.topRightLat - prefixBBox.bottomLeftLat) * (prefixBBox.topRightLon - prefixBBox.bottomLeftLon);
            }
            if(SAll/S < rate && prefixlen != prefixNow.length){
            	while(!searchQueue.isEmpty()){
            		long[] hashFromTo = new long[2];
            		BBoxPrefix prefix = searchQueue.poll();
            		hashFromTo[0] = prefix.prefix;
                    hashFromTo[1] = (0xffffffffffffffffL >>> prefix.length) + prefix.prefix;
                    ResultSet.add(hashFromTo);
            	}
            	break;
            }
            System.out.println(SAll/S+" "+SAll+" "+S+" "+prefixNow.length+" "+prefixlen+" "+bBoxPrefix.length+" "+searchQueue.size());
            prefixlen = prefixNow.length;
        }
      //hash 段的排序
        ResultSet.sort(new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return o1[0]>o2[0]?1:(o1[0]==o2[0]?0:-1);
			}
		});
//        hash 段的排序
        for(int i = 0; i < ResultSet.size()-1; i++){
//        	System.out.println(ResultSet.get(i)[0]+" "+ResultSet.get(i)[1]);
        	if(ResultSet.get(i)[1]+1 == ResultSet.get(i+1)[0]){
        		ResultSet.set(i+1,new long[]{ResultSet.get(i)[0],ResultSet.get(i+1)[1]});
        		ResultSet.remove(i);
        		i--;
        	}
        }
        System.out.println(SAll+" "+S+", "+ResultSet.size());
        return ResultSet;
    }

    /**
     * 圆的搜索，其实本质上是将圆转化为一个多边形，之后在利用多边形进行处理。
     * @param circle 字符串，圆心的横纵坐标，半径
     * @param deepth 查询深度
     * @return
     * @throws ParseException
     */
    public static ArrayList<long[]> searchCircleByDFS(String circle, int deepth) throws ParseException {
        System.err.println(circle);
    	//返回的结果
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        //JTS 中的内容
        GeometryFactory factory = JTSFactoryFinder.getGeometryFactory(null);
    	WKTReader reader = new WKTReader(factory);
        double topRightLat, bottomLeftLon, bottomLeftLat, topRightLon;
    	String[] arr = circle.split(",");
    	//3个元素 横纵坐标，半径
    	double x = Double.parseDouble(arr[0].trim()),
    			y = Double.parseDouble(arr[1].trim()),
    			r = Double.parseDouble(arr[2].trim());
    	bottomLeftLon = x - r;//经度，x
    	topRightLat = y + r;//纬度，y
    	topRightLon = x + r;
    	bottomLeftLat = y - r;
    	Point center = (Point) reader.read("POINT("+x+" "+y+")");
    	if(r <= 0){
    		System.err.println("圆的半径不能为非正数");
    		return null;
    	}
    	if(bottomLeftLon < -180 || topRightLat > 90 || topRightLon > 180 || bottomLeftLat < -90 ){
    		System.err.println("圆跨边界，暂不支持");
    		return null;
    	}

    	Polygon cir = createCircle(x, y, r, 32);
    	//外切正方形（矩形）。
        BBox searchBox = new BBox(topRightLat, bottomLeftLon, bottomLeftLat, topRightLon);
        System.out.println("search box:"+searchBox);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        System.out.println("prefix2Box:"+GeoHashUtil.PrefixToBBox(bBoxPrefix));
        Stack<BBoxPrefix> searchStack = new Stack<BBoxPrefix>();
        //init 将最开始的最大公共前缀放入，这里在栈中直接存储的是每个节点上对应的BBoxPrefix 虽然深度优先不会占用太多内存，(前缀的长度需要知道)
        searchStack.push(bBoxPrefix);
        //还是深度优先搜索二叉树
        while (!searchStack.empty()){
            BBoxPrefix prefixNow = searchStack.pop();
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            Polygon bB = box2Polygon(prefixBBox);
            //如果被包含了，那么停止，不再继续向下搜索
            if(cir.contains(bB)){
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }else if(prefixNow.length-bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                if(cir.intersects(box2Polygon(attachZeroBbox))){
                	searchStack.push(attachZero);
                }
                if(cir.intersects(box2Polygon(attachOneBbox))){
                	searchStack.push(attachOne);
                }
            }else {
                //超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }
        }
      //hash 段的排序
        ResultSet.sort(new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return o1[0]>o2[0]?1:(o1[0]==o2[0]?0:-1);
			}
		});
//        hash 段的排序
        for(int i = 0; i < ResultSet.size()-1; i++){
//        	System.out.println(ResultSet.get(i)[0]+" "+ResultSet.get(i)[1]);
        	if(ResultSet.get(i)[1]+1 == ResultSet.get(i+1)[0]){
        		ResultSet.set(i+1,new long[]{ResultSet.get(i)[0],ResultSet.get(i+1)[1]});
        		ResultSet.remove(i);
        		i--;
        	}
        }
        return ResultSet;
    }

    /**
     * 利用多边形来近似地模拟一个圆：构建一个圆的外接多边形，使多边形包含圆，
     * 利用该多边形来表示圆形
     * @param x 圆心横坐标
     * @param y 圆心纵坐标
     * @param R 圆半径
     * @param sides 模拟圆的多边形的边的数量
     * @return 返回一个模拟圆的多边形
     */
    private static Polygon createCircle(double x, double y, double R, int sides){
    	GeometryFactory factory = JTSFactoryFinder.getGeometryFactory(null);
    	final int SIDES = sides;//圆上面的点个数
		Coordinate coords[] = new Coordinate[SIDES+1];
		double L = R / Math.cos(Math.PI / SIDES);//外切多边形的顶点到圆形的距离
		for( int i = 0; i < SIDES; i++){
			double angle = ((double) i / (double) SIDES) * Math.PI * 2.0;
			double dx = Math.cos( angle ) * L;
			double dy = Math.sin( angle ) * L;
			coords[i] = new Coordinate( (double) x + dx, (double) y + dy );
		}
		coords[SIDES] = coords[0];
		LinearRing ring = factory.createLinearRing( coords );
		Polygon polygon = factory.createPolygon( ring, null );
		return polygon;
    }


    /**
     * 输入多边形或者圆形的字符串，找到一个最小的外切矩阵（各边水平或垂直，不考虑斜的情况）
     * 做一个关于参数的约定或者说明：当输入的参数代表的是一个圆时，polyCir 的结构是"x, y, r"
     * 当输入的参数表示的是一个多边形时，polyCir 的结构是"x1 y1, x2 y2, x3 y3, ... ,xn yn"
     * n显然是n>3
     * 返回左边界、右边界、上边界、下边界的数组
     * @param polyCir 代表圆形或者多边形的字符串
     * @return 长度为4的一维数组，分别存储左右上下边界的位置。
     */
    static double[] getMinRect(String polyCir){
    	double[] result = new double[4];
    	double left = 180, // left < 180，初始化
    			right = -180, // > -180
    			top = -90,// > -90
    			bottom = 90;// < 90
    	String[] point = polyCir.split(",");
    	if(point.length < 3){
    		try {
				throw new Exception("function getMinRect() Parameters error!");
			} catch (Exception e) {
				e.printStackTrace();
			}
    	}
    	if(point.length == 3){//表示一个圆
    		double x = Double.parseDouble(point[0]);
    		double y = Double.parseDouble(point[1]);
    		double r = Double.parseDouble(point[2]);
			result[0] = x - r;
			result[1] = x + r;
			result[2] = y + r;
			result[3] = y - r;
    	} else {
	    	for(int i = 0; i < point.length; i++){
				double x = Double.parseDouble(point[i].trim().split("\\s+")[0]);
				double y = Double.parseDouble(point[i].trim().split("\\s+")[1]);
				if( x < left){
					left = x;
				} else if(x > right){
					right = x;
				}
				if(y < bottom){
					bottom = y;
				} else if(y > top){
					top = y;
				}
			}
			result[0] = left;
			result[1] = right;
			result[2] = top;
			result[3] = bottom;
    	}
		return result;
    }

    /**
     * 将{@link BBox}类型，转化为jts.jar包中的{@linkplain com.vividsolutions.jts.geom.Polygon Polygon}类型，
     * 显然，这个Polygon只能是4个点的矩形。
     * @param box BBox对象
     * @return Polygon对象
     * @throws ParseException
     */
    static Polygon box2Polygon(BBox box) throws ParseException{
    	GeometryFactory factory = JTSFactoryFinder.getGeometryFactory(null);
    	WKTReader reader = new WKTReader(factory);
    	String bBStr = box.bottomLeftLon+" "+box.bottomLeftLat+","	//左下角点
        		+ box.topRightLon+" "+box.bottomLeftLat+"," //右下角
        		+ box.topRightLon+" "+box.topRightLat+"," //右上角
        		+ box.bottomLeftLon+" "+box.topRightLat+"," //左上角
        		+ box.bottomLeftLon+" "+box.bottomLeftLat; //左下角
    	Polygon poly = (Polygon) reader.read("POLYGON(("+bBStr+"))");
    	return poly;
    }



    /**
     * 专门用来对hash段进行排序，以及合并。排序的规则是以hash段的开始值(即左区间值)
     * 作为排序标准，合并的规则是如果在排序之后，2个hash段合并相连(即前一个hash段的
     * 右区间值与后一个hash段的左区间值相差1)
     *
     * @param arrayList 未合并的hash段
     * @return 合并之后的hash段。
     */
    private static void sortCombine(ArrayList<long[]> arrayList){
    	//hash 段的排序
        arrayList.sort(new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return o1[0]>o2[0]?1:(o1[0]==o2[0]?0:-1);
			}
		});
//        hash 段的合并
        for(int i = 0; i < arrayList.size()-1; i++){
        	if(arrayList.get(i)[1]+1 == arrayList.get(i+1)[0]){
        		arrayList.set(i+1,new long[]{arrayList.get(i)[0],arrayList.get(i+1)[1]});
        		arrayList.remove(i);
        		i--;
        	}
        }
    }
    /**
     * 调试用，输出ArrayList<long[]>中的元素
     * @param hashList
     */
    private static void show(ArrayList<long[]> hashList){
    	for(int i = 0; i < hashList.size(); i++){
    		System.out.println(hashList.get(i)[0]+" "+hashList.get(i)[1]);
//    		System.out.println(GeoHashUtil.HashToLongLat(hashList.get(i)[0])+"  "+GeoHashUtil.HashToLongLat(hashList.get(i)[1]));
//    		System.out.println(Long.toBinaryString(hashList.get(i)[0])+" "+Long.toBinaryString(hashList.get(i)[1]));
    	}
    }
    /**
     * 调试用，输出ArrayList<long[]>中hash段对应的矩形框的面积。
     * @param hashList
     * @return
     */
    private static double areas(ArrayList<long[]> hashList){
    	double S = 0.0;
    	for(int i = 0; i < hashList.size(); i++){
    		double blx = GeoHashUtil.HashToLongLat(hashList.get(i)[0]).getLongitude();
    		double bly = GeoHashUtil.HashToLongLat(hashList.get(i)[0]).getLatitude();
    		double TRx = GeoHashUtil.HashToLongLat(hashList.get(i)[1]).getLongitude();
    		double TRy = GeoHashUtil.HashToLongLat(hashList.get(i)[1]).getLatitude();
    		double dS = (TRx - blx)*(TRy-bly);
    		if(dS < 0){
    			System.err.println(dS);
    			dS = -dS;
    		}
//    		System.out.println(dS);
    		S += dS;
    	}
    	return S;
    }
    public static void main(String[] args) throws ParseException {
    	long t1 = System.currentTimeMillis();
    	ArrayList<long[]> hashList = getHashRange("p:2 2,5 2,5 5,2 5,2 2",false);
    	show(hashList);
    	System.out.println("-----------------------");
//    	System.out.println(areas(hashList));
//    	getHashRange("c:5,5,2",false);
    	long t2 = System.currentTimeMillis();
    	System.out.println("time:"+(t2-t1));
//    									 123456789012345678901234567890123456789012345678901234567890
//    	long a = Long.parseUnsignedLong("0000000000001111111111111111111111111111111111111111111111111111", 2);
//    	long b = Long.parseUnsignedLong("0000000000000000000000000000000000000000000000000000000000000000", 2);
//    	System.out.println(GeoHashUtil.HashToLongLat(a));
//    	System.out.println(GeoHashUtil.HashToLongLat(b));
//    	System.out.println(a - b);
//    	long hash = GeoHashUtil.LongLatToHash(5, 5);
//    	System.out.println(hash);
//    	String binHash = Long.toBinaryString(hash);
//    	System.out.println(binHash.length()+": "+binHash);
//    	a = Long.parseUnsignedLong(binHash, 2);
//    	System.out.println(a);
//    	long a = -4608097212474327040L;
//    	long b = -4608026843730149377L;
//    	long c = -4608026843730149376L;
//    	long d = -4607745368753438721L;
//    	long e = -4608237949962682368L;
//    	long f = -4608167581218504705L;
//    	System.out.println(GeoHashUtil.HashToLongLat(e)+" "+Long.toBinaryString(e));
//    	System.out.println(GeoHashUtil.HashToLongLat(f)+" "+Long.toBinaryString(f));
//    	System.out.println(GeoHashUtil.HashToLongLat(a)+" "+Long.toBinaryString(a));
//    	System.out.println(GeoHashUtil.HashToLongLat(b)+"  "+Long.toBinaryString(b));
//    	System.out.println(GeoHashUtil.HashToLongLat(c)+" "+Long.toBinaryString(c));
//    	System.out.println(GeoHashUtil.HashToLongLat(d)+"  "+Long.toBinaryString(d));

    }
}